package tree.treerecursion;

import tree.TreeNode;

/**
 * @Classname : SubtreeOfAnotherTree
 * @Description :
 * <a href="https://leetcode.cn/problems/subtree-of-another-tree/">572. 另一棵树的子树</a>
 * @Author : chentianyu
 * @Date 2023/1/20 09:40
 */


public class SubtreeOfAnotherTree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;

        // 先序遍历判断
        return isSame(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    // 判断两个树是否相等
    private boolean isSame(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;

        return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
    }
}
